//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。
//
// 示例 2：
//
//
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 100
//
//
// Related Topics 数组 动态规划 👍 1930 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//java:分割等和子集
public class Q0416PartitionEqualSubsetSum {
    public static void main(String[] args){
        Solution solution = new Q0416PartitionEqualSubsetSum().new Solution();
        solution.canPartition(new int[]{1,5,11,5});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canPartition(int[] nums) {
        // 转换为 「0 - 1」 背包问题
        // 该题 weights values都是nums
        if (nums == null || nums.length == 0 || nums.length> 200) return false;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) return false; // 奇数不考虑
        int n = nums.length, target = sum / 2;
        // 方法一
        // dp[i][j] 表示[0, i] 中能够找到一系列数等与j
//        boolean[][] dp = new boolean[n][target + 1];
//        for (int j = 0; j < target + 1; j++) {
//            if (nums[0] == j) {
//                dp[0][j] = true;
//            }
//        }
//        for (int i = 0; i < n; i++) {
//            dp[i][0] = true;
//        }
//        for (int i = 1; i < n; i++) {
//            for (int j = 1; j < target + 1; j++) {
//                // j < nums[i], 取上一次的状态,不使用当前数字
//                dp[i][j] = dp[i - 1][j];
//                // 必然true，选当前值
//                if (nums[i] == j) {
//                    dp[i][j] = true;
//                    continue;
//                }
//                // 考虑使用当前数据，取上一次的目标j，或者上一次不选择当前nums[i] 的值
//                if (nums[i] < j)  dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
//            }
//        }
//        return dp[n - 1][target];

        // 方法二
        // dp[j] 表示 容量为j的背包中 能放入的最大数值
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}